#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

#define SIZE 100000

// See slide 7, chapter 6 (modified to use left and right instead of n)
void InsertionSort(int *A, int left, int right) {
  for(int p = left + 1; p <= right; p++) {
    int key = A[p];
    int i = p - 1;
    while(i >= 0 && A[i] > key) {
      A[i + 1] = A[i];
      i--;
    }
    A[i + 1] = key;
  }
}

////////////////////////////////////////////////////////////

// Swap the array elements at indexes i and j.
void swap(int *A, int i, int j) {
  int temp = A[i];
  A[i] = A[j];
  A[j] = temp;
}

// See slide 24, chapter 7
void Median3(int *A, int left, int right) {
  int center = (left + right) / 2;

  // Make sure that A[left] is smaller than both A[center] and A[right]:
  if(A[left] > A[center]) {
    swap(A, left, center);
  }
  if(A[left] > A[right]) {
    swap(A, left, right);
  }
  // Now make sure that A[center] is smaller than A[right]:
  if(A[center] > A[right]) {
    swap(A, center, right);
  }
  // Put the pivot at second last position:
  swap(A, center, right - 1);
}

// See slide 26, chapter 7
int Partition(int *A, int left, int right) {
  Median3(A, left, right);
  
  int i = left + 1;
  int j = right - 2;
  int pivot = A[right - 1];

  while(true) {
    while(A[i] < pivot) {
      i++;
    }
    while(A[j] > pivot) {
      j--;
    }
    if(i < j) {
      swap(A, i, j);
      i++;
      j--;
    } else {
      break; // end of while loop
    }
  }
  swap(A, i, right - 1);
  return i; // index of pivot after last swap
}

// See slide 19, chapter 7
void QuickSort(int *A, int left, int right) {
  if(right - left <= 10) {
    InsertionSort(A, left, right);
    return;
  }

  int q = Partition(A, left, right);
  QuickSort(A, left, q - 1);
  QuickSort(A, q + 1, right);
}

////////////////////////////////////////////////////////////

// See slide 24, chapter 8
bool Insert(int *A, int size, int x) {
  // Note: based on the way the Insert function is used below in HeapSort,
  // we know that the following test can never fail.
  if(size == SIZE) {
    return false;
  }
  // Percolate up:
  int hole = size++;
  while(hole > 0 && x > A[(hole - 1) / 2]) {
    A[hole] = A[(hole - 1) / 2];
    hole = (hole - 1) / 2;
  }
  A[hole] = x;
  return true;
}

// See slide 29, chapter 8
int deleteMax(int *A, int size) {
  // Note: based on the way the Insert function is used below in HeapSort,
  // we know that the following test can never fail.
  if(size == 0) {
    return -1; // to differentiate from the array's content
  }
  int max = A[0];
  int hole = 0;
  int x = A[--size];

  // Percolate down:
  while(2 * hole + 1 < size) { // the hole has at least a left child
    int sid;
    if(2 * hole + 2 < size) { // the hole also has a right child
      sid = A[2 * hole + 1] > A[2 * hole + 2] ? 2 * hole + 1 : 2 * hole + 2;
    } else {
      sid = 2 * hole + 1; // only a left child exists
    }
    if(x >= A[sid]) {
      break; // end of while loop
    }
    A[hole] = A[sid];
    hole = sid;
  }
  A[hole] = x;
  return max;
}

// See slide 38, chapter 8
void HeapSort(int *A, int n) {
  for(int i = 0; i < n; i++) {
    Insert(A, i, A[i]);
  }
  for(int i = n - 1; i >= 0; i--) {
    A[i] = deleteMax(A, i + 1);
  }
}

////////////////////////////////////////////////////////////

int main(void) {
  int A1[SIZE], A2[SIZE];

  // Initialize pseudo-random number genrator:
  srand(time(NULL));
  // And fill in the arrays:
  for(int i = 0; i < SIZE; i++) {
    A2[i] = A1[i] = rand();
  }

  clock_t start = clock();
  QuickSort(A1, 0, SIZE - 1);
  clock_t end = clock();
  printf("Quick Sort: %f ms\n", 1000.0 * (double)(end - start) / CLOCKS_PER_SEC);

  start = clock();
  HeapSort(A2, SIZE);
  end = clock();
  printf("Heap Sort: %f ms\n", 1000.0 * (double)(end - start) / CLOCKS_PER_SEC);

  return 0;
}
